package com.ljy.my_study.leetcode.medium.O_1_时间插入删除和获取随机元素;

import java.util.*;

/**
 * @author: li.junying
 * @create: 2022-04-13 09:17
 */
public class RandomizedSet {

    List<Integer> list;
    Map<Integer,Integer> map;
    Random random;

    public RandomizedSet() {
        list=new ArrayList<>();
        map=new HashMap<>();
        random=new Random();
    }

    public boolean insert(int val) {
        if(map.containsKey(val)){
            return false;
        }
        int index=list.size();
        list.add(val);
        map.put(val,index);
        return true;
    }

    public boolean remove(int val) {
        if(!map.containsKey(val)){
            return false;
        }
//        int last=list.size()-1;
        Integer lastValue=list.get(list.size()-1);
        Integer index=map.get(val);
        map.put(lastValue,index);
        map.remove(val);
        list.set(index,lastValue);
        list.remove(list.size()-1);
        return true;
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}
